package com.atguigui.leetcode;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

/**
 * 895.最大频率栈
 * Project: leetcode
 * Package: com.atguigui.leetcode
 * Version: 1.0
 * <p>
 * Created by WJX on 2022/11/30 14:30
 */
public class P895MaximumFrequencyStack {
    public static void main(String[] args) {
        FreqStack solution = new P895MaximumFrequencyStack().new FreqStack();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class FreqStack {
        //记录数字出现的个数
        private Map<Integer, Integer> freq;
        private Map<Integer, Deque<Integer>> group;
        private int maxFreq;

        public FreqStack() {
            freq = new HashMap<>();
            group = new HashMap<>();
            maxFreq = 0;
        }

        public void push(int val) {
            freq.put(val, freq.getOrDefault(val, 0) + 1);
            //数字对应的栈
            group.putIfAbsent(freq.get(val), new ArrayDeque<Integer>());
            //放入对应的栈，如果出现的次数相同，则会进入同一个栈
            group.get(freq.get(val)).push(val);
            maxFreq = Math.max(maxFreq, freq.get(val));
        }

        public int pop() {
            int val = group.get(maxFreq).peek();
            //更新个数
            freq.put(val, freq.get(val) - 1);
            //吐出一个
            group.get(maxFreq).pop();
            if (group.get(maxFreq).isEmpty()) {
                maxFreq--;
            }
            return val;
        }
    }
}
